package com.breeze.leetcode;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
 * 350. 两个数组的交集 II
 * 给定两个数组，编写一个函数来计算它们的交集。
 * <p>
 * <p>
 * 说明：
 * <p>
 * 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
 * 我们可以不考虑输出结果的顺序。
 * <p>
 * 进阶:
 * 如果给定的数组已经排好序呢？你将如何优化你的算法？
 * 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
 * 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
 */
public class LeetCode350 {
    /**
     * 方法1：利用List的remove方法来判断重复
     * 时间复杂度：O(m+n)
     * 空间复杂度：O(min(m,n))
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        List<Integer> list1 = new LinkedList<>();
        for (int i = 0; i < nums1.length; i++) {
            list1.add(nums1[i]);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (list1.remove(Integer.valueOf(nums2[i]))) {
                intersection[index++] = nums2[i];
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }

    /**
     * 方法2：针对方法1，使用字典来提高性能
     */
    public int[] intersect1(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        // key存储数值，value存储数值出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }

    /**
     * 进阶： 如果给定的数组已经排好序呢？你将如何优化你的算法？
     */
    public int[] intersect2(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] intersection = new int[nums1.length];
        int index = 0;
        // 双指针
        int p1 = 0, p2 = 0;
        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] < nums2[p2]) {
                p1++;
            } else if (nums1[p1] > nums2[p2]) {
                p2++;
            } else {
                intersection[index++] = nums1[p1];
                p1++;
                p2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }

    public static void main(String[] args) {
        int[] nums1 = {9, 11, 13};
        int[] nums2 = {2, 3, 4, 5, 8, 9, 10, 13};
        LeetCode350 leetCode350 = new LeetCode350();
        int[] intersect = leetCode350.intersect2(nums1, nums2);
        for (int i : intersect) {
            System.out.print(i + ",");
        }
    }
}
